import java.util.*;

public class Sort {
    public static void main(String[] args) {
        int[] array = new int[]{4, 5,3,2,1};
        System.out.print("原数组：");
        System.out.println(Arrays.toString(array));
        List<Integer> l;

        l = new ArrayList<>(Arrays.stream(array).boxed().toList());
        System.out.print("冒泡排序：");
        System.out.println(bubbleSort(l));

        l = new ArrayList<>(Arrays.stream(array).boxed().toList());
        System.out.print("快速排序：");
        System.out.println(quickSort(l));

        l = new ArrayList<>(Arrays.stream(array).boxed().toList());
        System.out.print("选择排序：");
        System.out.println(selectSort(l));

        l = new ArrayList<>(Arrays.stream(array).boxed().toList());
        System.out.print("插入排序：");
        System.out.println(insertSort(l));

        l = new ArrayList<>(Arrays.stream(array).boxed().toList());
        System.out.print("堆排序：");
        System.out.println(heapSort(l));

    }

    public static <T> void swap(List<T> array, int a, int b){
        T tmp = array.get(a);
        array.set(a, array.get(b));
        array.set(b, tmp);
    }

    public static List<Integer> bubbleSort(List<Integer> array) {
        int n = array.size();
        for (int i = 0; i < n; i++) {
            boolean flag = false;
            for (int j = 0; j < n-i-1; j++ ) {
                if (array.get(j) > array.get(j+1)) {
                    swap(array, j, j+1);
                    flag = true;
                }
            }
            if (!flag) break;
        }
        return array;
    }

    public static List<Integer> quickSort(List<Integer> array){
        qSort(array, 0, array.size()-1);
        return array;
    }

    private static void qSort(List<Integer> array, int left, int right){
        // 边界条件：子数组长度不为0
        if (left < right) {
            int pointer = partition(array, left, right);
            // 分治
            qSort(array, left, pointer-1);
            qSort(array, pointer+1, right);
        }
    }

    private static int partition(List<Integer> array, int left, int right){
        Integer pivot = array.get(right);   // 选最后一个数作为轴
        int pointer = left;                 // 指针，保证指针前的数字都比轴小

        for (int i = left; i < right; i++ ){
            if (array.get(i) < pivot){
                swap(array, i, pointer);    // 遍历，将小于轴的数字置换到前面
                pointer++;
            }
        }
        swap(array, pointer, right);    // 把轴置换到指针处
        return pointer;
    }

    public static List<Integer> heapSort(List<Integer> array){
        int heapLength = array.size();
        for (int i = heapLength / 2 - 1; i > 0; i--) {
            heapify(array, i, heapLength);
        }

        while (heapLength > 0){
            heapify(array, 0, heapLength);
            heapLength--;
            swap(array, 0, heapLength);
        }

        return array;
    }

    private static void heapify(List<Integer> array, int current, int heapLength){

        int target = current;       // 当前最大元素所在位置

        int left = 2*current+1;
        if (left < heapLength && array.get(left) > array.get(target)){
            target = left;
        }

        int right = 2*current+2;
        if (right < heapLength && array.get(right) > array.get(target)){
            target = right;
        }

        if (target != current) {
            swap(array, current, target);
            heapify(array, target, heapLength);
        }
    }

    public static List<Integer> selectSort(List<Integer> array){
        int minIndex;
        for (int i = 0; i < array.size(); i++) {
            minIndex = i;
            for (int j = i; j < array.size(); j++) {
                if (array.get(j) < array.get(minIndex))
                    minIndex = j;
            }
            swap(array, i, minIndex);
        }
        return array;
    }
    
    public static List<Integer> insertSort(List<Integer> array){
        int preIndex, current;
        for (int i = 1; i < array.size(); i++) {
            preIndex = i-1;
            current = array.get(i);
            while (preIndex >= 0 && current < array.get(preIndex)) {
                array.set(preIndex+1, array.get(preIndex));
                preIndex--;
            }
            array.set(preIndex+1, current);
        }
        return array;
    }
    public static List<Integer> sort(List<Integer> array){
        return null;
    }

}
